package com.zofer.study.tree;

/**
 * 题目：给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。
 * 设 t1 树的边集为 E1，t2 树的边集为 E2，若 E2 等于 E1 ，则表示 t1 树和t2 树的拓扑结构完全相同。
 */
public class ContainsSubTree {

    /**
     * 首先判断一个树是否是另一棵树的子树，很明显想到可以用递归，
     * 但是两棵树完全相同也可以看做一棵树是另一棵树的子树。
     * 所以自然而然想到用一个判断两棵树是否相同的递归函数。
     * @param root1
     * @param root2
     * @return
     */
    boolean isContains (TreeNode root1, TreeNode root2){
        // write code here
        if(root2 == null) return true;
        if(root1 == null) return false;
        return isContains(root1.left,root2) || isContains(root1.right,root2) || isSame(root1,root2);
    }

    //判断两颗树是否相同
    boolean isSame(TreeNode node1,TreeNode node2){
        if(node1 == null && node2 == null) return true;
        if(node1 == null || node2 == null) return false;
        if(node1.val != node2.val) return false;
        return isSame(node1.left,node2.left) && isSame(node1.right,node2.right);
    }
}
